// https://www.lintcode.com/problem/search-a-2d-matrix/description

class Solution {
public:
    /**
     * @param matrix: matrix, a list of lists of integers
     * @param target: An integer
     * @return: a boolean, indicate whether matrix contains target
     */
    bool searchMatrix(vector<vector<int>> &matrix, int target) {
        // 两次binary
//         if (matrix.empty()) return false;
//         int low = 0;
//         int high = matrix.size() - 1;
//         int tmp = 0;
//         while (low + 1 < high)
//         {
//             int mid = (high - low) / 2 + low;
//             if (matrix[mid][0] == target) return true;
//             else if (matrix[mid][0] < target) low = mid;
//             else high = mid;
//         }
//         if (matrix[high][0] <= target) tmp = high;
//         else if (matrix[low][0] <= target) tmp = low;
//         else return false;
// // 注意是<=
// // Input
// // [[1,4,5],[6,7,8]]
// // 6
// // Expected
// // true
//         low = 0;
//         high = matrix[0].size() - 1;
//         while (low + 1 < high)
//         {
//             int mid = (high - low) / 2 + low;
//             if (matrix[tmp][low] == target) return true;
//             else if (matrix[tmp][low] < target) low = mid;
//             else high = mid;
//         }
//         if (matrix[tmp][low] == target || matrix[tmp][high] == target) return true;
//         return false;


        // 一次binary
        if (matrix.empty()) return false;
        int m = matrix.size();
        int n = matrix[0].size();
        int low = 0;
        int high = m * n - 1;
        while (low + 1 < high)
        {
            int mid = (high - low) / 2 + low;
            if (matrix[mid / n][mid % n] == target) return true;
            else if (matrix[mid / n][mid % n] < target) low = mid;
            else high = mid;
        }
        if (matrix[low / n][low % n] == target || matrix[high / n][high % n] == target) return true;
        else return false;
    }
    
};